#include <iostream>

using namespace std;

/*
There are 0-4 characters on the phone pad key for each number. 
Given the numbers, printing all possible word combinations(0, 1 can be taken as ??.
*/

char Pad[10][4] = {{'+'},{'#'},{'a','b','c'},{'d','e','f'},{'g','h','i'},{'j','k','l'},{'m','n','o'},{'p','q','r','s'},{'t','u','v'},{'w','x','y','z'}};
int PadCount[10] = {1,1,3,3,3,3,3,4,3,4};

bool PrintNumberRecur( char *OrgStr, char* OutStr, int Length, int Cur)
{
	if( Cur == Length )
	{
		cout<<OutStr<<endl;
		return true;
	}

	if( OrgStr[Cur]>'9' || OrgStr[Cur]<'0' )
	{
		cout<<"Invalid input"<<endl;
		return false;;
	}

	int index = OrgStr[Cur]-'0';
	for( int i=0; i<PadCount[index]; i++ )
	{
		OutStr[Cur] = Pad[index][i];
		if(!PrintNumberRecur(OrgStr, OutStr, Length, Cur+1))
			return false;
	}
	return true;
}

void PrintPhoneNumber( char *str )
{
	int strLength = strlen(str);
	char* outputStr = new char[strLength+1];
	outputStr[strLength] = '\0';

	PrintNumberRecur( str, outputStr, strLength, 0 );
	
	delete [] outputStr;
}

int main()
{
	char str[]="2134";
	cout<<"convert "<<str<<endl;
	PrintPhoneNumber( str);
	cout<<'\n'<<endl;

	char str2[]="2433";
	cout<<"convert "<<str2<<endl;
	PrintPhoneNumber(str2);
	cout<<'\n'<<endl;

	char str3[]="ab23";
	cout<<"convert "<<str3<<endl;
	PrintPhoneNumber( str3);
	cout<<'\n'<<endl;

	cout<<"Press any key to terminate..."<<endl;
	return getchar();
}